package week_5.homework;
/*程序设计项目pp9.3，修改本章中所示的排序法（选择、插入、冒泡、快速、归并）
* 在每个排序法中添加代码以使得他们能够对总的比较次数和每一算法的总执行时间进行计数。
* 在同一列表上执行这些排序算法，并记录下有关每一算法总比较次数和总执行时间的信息。
* 请尝试使用不同的列表，且至少包括一个已经排好序的列表。*/
public class NewSorting {
    //选择排序
    public static <T extends Comparable<T>> void selectionSort(T[] data)
    {
        int min;
        T temp;
        long startTime=System.nanoTime();   //获取开始时间
        int comparetimes = 0;//总的比较次数

        for (int index = 0; index < data.length-1; index++)
        {
            comparetimes++;
            min = index;
            for (int scan = index+1; scan < data.length; scan++) {
                if (data[scan].compareTo(data[min]) < 0)
                    min = scan;
                comparetimes++;
            }
            swap(data, min, index);
        }

        long endTime = System.nanoTime(); //获取结束时间
        System.out.println("选择排序总运行时间： "+(endTime-startTime)+"ns");
        System.out.println("选择排序总的比较次数："+comparetimes);
    }
    //swap方法
    private static <T extends Comparable<T>> void swap(T[] data, int index1, int index2)
    {
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
    //插入排序
    public static <T extends Comparable<T>> void insertionSort(T[] data)
    {
        long startTime=System.nanoTime();   //获取开始时间
        int comparetimes = 0;//总的比较次数
        for (int index = 1; index < data.length; index++)
        {
            T key = data[index];
            int position = index;

            // shift larger values to the right
            while (position > 0 && data[position-1].compareTo(key) > 0)
            {
                data[position] = data[position-1];//把数值大的数换到了右边
                position--;//position变成左边数的索引
                comparetimes++;
            }
            data[position] = key;
            comparetimes++;
        }

        long endTime = System.nanoTime(); //获取结束时间
        System.out.println("插入排序总运行时间： "+(endTime-startTime)+"ns");
        System.out.println("插入排序总的比较次数："+comparetimes);
    }
    //冒泡排序
    public static <T extends Comparable<T>> void bubbleSort(T[] data)
    {
        int position, scan;
        T temp;
        long startTime=System.nanoTime();   //获取开始时间
        int comparetimes = 0;//总的比较次数
        for (position =  data.length - 1; position >= 0; position--)
        {
            comparetimes++;
            for (scan = 0; scan <= position - 1; scan++)
            {
                if (data[scan].compareTo(data[scan+1]) > 0)
                    swap(data, scan, scan + 1);
                comparetimes++;
            }//第一个循环里面是第一次两个两个比较到列表末尾
        }//第二个循环里面是一共进行内循环的次数，其次数与列表元素个数-1相等

        long endTime = System.nanoTime(); //获取结束时间
        System.out.println("冒泡排序总运行时间： "+(endTime-startTime)+"ns");
        System.out.println("冒泡排序总的比较次数："+comparetimes);
    }
    //归并排序
    private static int comparetimes = 0;//总的比较次数
    public static <T extends Comparable<T>> void mergeSort(T[] data)
    {
        long startTime=System.nanoTime();   //获取开始时间
        mergeSort(data, 0, data.length - 1);

        long endTime = System.nanoTime(); //获取结束时间
        System.out.println("归并排序总运行时间： "+(endTime-startTime)+"ns");
        System.out.println("归并排序总的比较次数："+comparetimes);
    }
    private static <T extends Comparable<T>> void mergeSort(T[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort(data, min, mid);
            mergeSort(data, mid+1, max);
            merge(data, min, mid, max);
        }
        comparetimes++;
    }
    private static <T extends Comparable<T>>
    void merge(T[] data, int first, int mid, int last)
    {
        T[] temp = (T[])(new Comparable[data.length]);

        int first1 = first, last1 = mid;  // endpoints of first subarray第一个子数组的端点
        int first2 = mid+1, last2 = last;  // endpoints of second subarray第二个子数组的端点
        int index = first1;  // next index open in temp array

        //  Copy smaller item from each subarray into temp until one
        //  of the subarrays is exhausted
        while (first1 <= last1 && first2 <= last2)
        {
            if (data[first1].compareTo(data[first2]) < 0)
            {
                temp[index] = data[first1];
                first1++;
            }
            else
            {
                temp[index] = data[first2];
                first2++;
            }
            index++;
        }

        //  Copy remaining elements from first subarray, if any
        while (first1 <= last1)
        {
            temp[index] = data[first1];
            first1++;
            index++;
        }

        //  Copy remaining elements from second subarray, if any
        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
        }

        //  Copy merged data into original array
        for (index = first; index <= last; index++)
            data[index] = temp[index];
    }
    //快速排序
    private static int time=0;
    public static <T extends Comparable<T>> void quickSort(T[] data)
    {
        long startTime=System.nanoTime();   //获取开始时间
        quickSort(data, 0, data.length - 1);

        long endTime = System.nanoTime(); //获取结束时间
        System.out.println("快速排序总运行时间： "+(endTime-startTime)+"ns");
        System.out.println("快速排序总的比较次数："+time);
    }
    private static <T extends Comparable<T>> void quickSort(T[] data, int min, int max)
    {
        time++;
        if (min < max)
        {
            // create partitions
            int indexofpartition = partition(data, min, max);

            // sort the left partition (lower values)
            quickSort(data, min, indexofpartition - 1);

            // sort the right partition (higher values)
            quickSort(data, indexofpartition + 1, max);
        }
    }
    private static <T extends Comparable<T>> int partition(T[] data, int min, int max)
    {
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;

        // use the middle data value as the partition element
        partitionelement = data[middle];
        // move it out of the way for now
        swap(data, middle, min);

        left = min;
        right = max;

        while (left < right)
        {
            // search for an element that is > the partition element
            while (left < right && data[left].compareTo(partitionelement) <= 0)
                left++;

            // search for an element that is < the partition element
            while (data[right].compareTo(partitionelement) > 0)
                right--;

            // swap the elements
            if (left < right)
                swap(data, left, right);
        }

        // move the partition element into place
        swap(data, min, right);

        return right;
    }
}
